#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>
using namespace std;

struct Event {
    int time;
    int car_id;
    int current_node;
    Event(int t, int c, int n) : time(t), car_id(c), current_node(n) {}
    bool operator<(const Event& e) const {
        return time > e.time;
    }
};

vector<int> dijkstra(int N, int start, int end, int** roadlength, int** flow, int** restrictions) {
    int* dist = new int[N];
    int* prev = new int[N];
    bool* visited = new bool[N];
    for (int i = 0; i < N; i++) {
        dist[i] = INT_MAX;
        visited[i] = false;
    }
    dist[start] = 0;
    prev[start] = -1;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(0, start));
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if (visited[u]) continue;
        visited[u] = true;
        for (int v = 0; v < N; v++) {
            if (roadlength[u][v] < INT_MAX && flow[u][v] < restrictions[u][v]) {
                if (dist[v] > dist[u] + roadlength[u][v]) {
                    dist[v] = dist[u] + roadlength[u][v];
                    prev[v] = u;
                    pq.push(make_pair(dist[v], v));
                }
            }
        }
    }
    vector<int> path;
    int node = end;
    while (node != -1) {
        path.push_back(node);
        node = prev[node];
    }
    reverse(path.begin(), path.end());
    delete[] dist;
    delete[] prev;
    delete[] visited;
    return path;
}

int main() {
    int N, M;
    cin >> N >> M;
    int** roadlength = new int*[N];
    int** restrictions = new int*[N];
    int** cars = new int*[M];
    for (int i = 0; i < N; i++) {
        roadlength[i] = new int[N];
        restrictions[i] = new int[N];
    }
    for (int i = 0; i < M; i++) {
        cars[i] = new int[2];
    }
    // 读取 roadlength
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> roadlength[i][j];
            if (roadlength[i][j] == 0 && i != j) roadlength[i][j] = INT_MAX;
        }
    }
    // 读取 restrictions
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> restrictions[i][j];
        }
    }
    // 读取 cars
    for (int i = 0; i < M; i++) {
        cin >> cars[i][0] >> cars[i][1];
        cars[i][0]--;
        cars[i][1]--;
    }
    // 初始化 flow
    int** flow = new int*[N];
    for (int i = 0; i < N; i++) {
        flow[i] = new int[N];
        for (int j = 0; j < N; j++) {
            flow[i][j] = 0;
        }
    }
    // 为每辆车找到初始路径，并设置事件
    priority_queue<Event> event_queue;
    vector<vector<int>> paths(M);
    vector<int> car_arrival_time(M, -1);
    for (int i = 0; i < M; i++) {
        paths[i] = dijkstra(N, cars[i][0], cars[i][1], roadlength, flow, restrictions);
        if (paths[i].size() == 0) {
            // 无法到达，处理错误
            continue;
        }
        if (paths[i].size() > 1) {
            int u = paths[i][0];
            int v = paths[i][1];
            int time = roadlength[u][v];
            event_queue.push(Event(time, i, v));
            flow[u][v]++;
            flow[v][u]++;
            paths[i].push_back(v); // 记录当前所在节点
        } else {
            // 已经在目的地
            car_arrival_time[i] = 0;
            paths[i].push_back(cars[i][0]);
        }
    }
    // 模拟过程
    vector<int> to_plan;
    while (!event_queue.empty()) {
        int current_time = event_queue.top().time;
        // Process all events with time == current_time
        vector<Event> current_events;
        while (!event_queue.empty() && event_queue.top().time == current_time) {
            current_events.push_back(event_queue.top());
            event_queue.pop();
        }
        // First, process all arrivals: update flows
        for (Event e : current_events) {
            int car_id = e.car_id;
            int current_node = e.current_node;
            // If the car has not arrived yet
            if (car_arrival_time[car_id] == -1) {
                // Remove the car from the current road
                if (paths[car_id].size() > 1) {
                    int u = paths[car_id][paths[car_id].size() - 2];
                    int v = paths[car_id].back();
                    flow[u][v]--;
                    flow[v][u]--;
                }
                // Check if the car has reached the destination
                if (current_node == cars[car_id][1]) {
                    car_arrival_time[car_id] = current_time;
                    // Update the path to include the destination
                    paths[car_id].push_back(current_node);
                } else {
                    // Car hasn't reached yet; plan the next move
                    // Collect car_ids to plan next moves after all arrivals are processed
                    to_plan.push_back(car_id);
                }
            }
        }
        // Now, plan the next moves for the cars that arrived at intermediate nodes
        for (int car_id : to_plan) {
            // Plan the next path with the updated flow
            vector<int> new_path = dijkstra(N, paths[car_id].back(), cars[car_id][1], roadlength, flow, restrictions);
            if (new_path.size() == 0) {
                // No path available; car waits for the next time step
                event_queue.push(Event(current_time + 1, car_id, paths[car_id].back()));
            } else {
                // Update the path
                paths[car_id] = new_path;
                // Schedule the next event
                if (paths[car_id].size() > 1) {
                    int u = paths[car_id][0];
                    int v = paths[car_id][1];
                    flow[u][v]++;
                    flow[v][u]++;
                    int travel_time = current_time + roadlength[u][v];
                    event_queue.push(Event(travel_time, car_id, v));
                    // Update the path to include the current position
                    paths[car_id].push_back(v);
                } else {
                    // Shouldn't happen, as the car hasn't arrived yet
                    // Maybe handle error
                }
            }
        }
        // Clear the to_plan list for the next time step
        to_plan.clear();
    }
    // 输出每辆车的行驶路线
    for (int i = 0; i < M; i++) {
        cout << "Car " << i << " path: ";
        if (paths[i][0]!=cars[i][0])cout<<cars[i][0]+1<<" ";
        for (int node : paths[i]) {
            cout << node + 1;
            if (node!=cars[i][1])cout<<" ";
            else break;
        }
        cout << endl;
    }
    // 输出总耗时
    int sum = 0;
    for (int i = 0; i < M; i++) {
        sum += car_arrival_time[i];
    }
    cout << "Total time: " << sum << endl;
    // 释放内存
    for (int i = 0; i < N; i++) {
        delete[] roadlength[i];
        delete[] restrictions[i];
        delete[] flow[i];
    }
    delete[] roadlength;
    delete[] restrictions;
    delete[] flow;
    for (int i = 0; i < M; i++) {
        delete[] cars[i];
    }
    delete[] cars;
    return 0;
}